package digitRecognitionProblem;

import genetic_algorithm.Selection;

import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;

import utils.RandomGenerator;

public class DigitRecognitionSelector extends Selection {

	public DigitRecognitionSelector(boolean remove) {
		super(remove);
	}

	@Override
	protected Entry<Integer, Integer> selectPair() {

		// return two best chromosomes
		int numChromosomes = population.getSize();		
		
		/*
		 * initialize look-up table implementing roulette wheel selection:
		 * element's key is chromosome's index in population, value is chromosome's
		 * probability to be chosen (proportional to its fitness)
		 */
		List<Entry<Integer, Double>> lookup = new ArrayList<Entry<Integer, Double>>(numChromosomes);
		
		/* 
		 * create entry in lookup table for each chromosome:
		 * add chromosomes in increasing order of fitness
		 */		
		double currFitness = 0.0;
		for (int i = 0 ; i < numChromosomes ; ++i) {
 
			// calculate fitness for current chromosome
			currFitness= population.getFitnessOfChromosome(i);
			
			// add chromsome's entry
			lookup.add(new AbstractMap.SimpleEntry<Integer, Double>(i, currFitness));
		}
				
		/*
		 * choose pair of chromosomes (relying on the probabilities):
		 * choose a number from 0 to total fitness. 
		 * iterate over lookup table and accumulate fitness of each chromosome. 
		 * when reaches a chromosme whose accumulated value is at least the chosen
		 * number, pick this chromosome and start over again
		 */
		List<Integer> chosen = new ArrayList<Integer>();
		double totalFitness = sumFitness(numChromosomes);
		while (chosen.size() < 2) { // keep scanning lookup table until two are chosen

			double accFitness = 0.0; // accumulated fitness
			
			// choose minimal accumulated fitness value
			double threshold = RandomGenerator.nextInt((int) totalFitness);
			
			// choose chromosomes according to their probability
			Iterator<Entry<Integer,Double>> itr = lookup.iterator();
			while (itr.hasNext() && (chosen.size() < 2)) {
				
				// accumulate fitness values
				Entry<Integer, Double> currEntry = itr.next();				
				accFitness += currEntry.getValue();
				
				// check if can choose current chromosome
				if (threshold <= accFitness) {
					
					// add chromosome to return value
					chosen.add(currEntry.getKey());
					
					// remove from lookup table (parents must be different)
					itr.remove();
				}
			}
		}
		
		// return indices of parents
		return new AbstractMap.SimpleEntry<Integer, Integer>(chosen.get(0), chosen.get(1));
	}

	private double sumFitness(int numChromosomes) {

		double totalFitness = 0.0;
		for (int i = 0 ; i < numChromosomes ; ++i) {
			totalFitness += population.getFitnessOfChromosome(i);
		}
		return totalFitness;
	}
}
